//DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。 
//
// 
// 例如， "ACGAATTCCG" 是一个 DNA序列 。 
// 
//
// 在研究 DNA 时，识别 DNA 中的重复序列非常有用。 
//
// 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
//输出：["AAAAACCCCC","CCCCCAAAAA"]
// 
//
// 示例 2： 
//
// 
//输入：s = "AAAAAAAAAAAAA"
//输出：["AAAAAAAAAA"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 10⁵ 
// s[i]=='A'、'C'、'G' or 'T' 
// 
// Related Topics 位运算 哈希表 字符串 滑动窗口 哈希函数 滚动哈希 👍 385 👎 0

package leetcode.editor.cn;

import java.util.*;

class RepeatedDnaSequences {
    public static void main(String[] args) {
        Solution solution = new RepeatedDnaSequences().new Solution();
        solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 暴力解法 O(NL)
        /*public List<String> findRepeatedDnaSequences(String s) {
            // 两个都需要去重
            Set<String> set = new HashSet<>();
            Set<String> res = new HashSet<>();

            for (int i = 0; i <= s.length() - 10; i++) {
                String substring = s.substring(i, i + 10);
                if (set.contains(substring)) {
                    res.add(substring);
                } else {
                    set.add(substring);
                }
            }

            return new LinkedList<>(res);
        }*/

        public List<String> findRepeatedDnaSequences(String s) {
            // 将s的A G C T使用数字表示
            char[] array = s.toCharArray();
            for (int i = 0; i < array.length; i++) {
                switch (s.charAt(i)) {
                    case 'A':
                        array[i] = 0;
                        break;
                    case 'G':
                        array[i] = 1;
                        break;
                    case 'C':
                        array[i] = 2;
                        break;
                    case 'T':
                        array[i] = 3;
                        break;
                }
            }

            int R = 4;  // 表示4进制
            int L = 10; // 表示多少位
            int RL = (int) Math.pow(R, L - 1);   // 存储 R^(L - 1) 的结果，用于删除最高位

            int left = 0, right = 0;
            HashSet<Integer> seen = new HashSet<>();
            HashSet<String> res = new HashSet<>();
            int windowHash = 0;

            while (right < array.length) {
                windowHash = windowHash * R + array[right];
                right++;

                if (right - left == L) {
                    if (!seen.contains(windowHash)) {
                        seen.add(windowHash);
                    } else {
                        String substring = s.substring(left, right);
                        res.add(substring);
                    }


                    // 移动窗口
                    windowHash = windowHash - array[left] * RL;
                    left++;
                }
            }

            return new LinkedList<>(res);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
